#include<bits/stdc++.h>
using namespace std;
class Trie
{
    public:
        Trie()
        {   
            childs=vector<Trie*>(26);
            flag=false;
        }
        void insert(string s)
        {
            Trie* node=this;
            for(char ch:s)
            {
                ch-='a';
                if(node->childs[ch]==nullptr) node->childs[ch]=new Trie();
                node=node->childs[ch];
            }
            node->flag=true;
        }
        Trie* searchpre(string s)
        {
            Trie* node=this;
            for(char ch:s)
            {
                ch-='a';
                if(node->childs[ch]==nullptr) return nullptr;
                node=node->childs[ch];
            }
            return node;
        }
        bool search(string s)
        {
            Trie* node=this->searchpre(s);
            return node!=nullptr&&node->flag;
        }
        bool startsWith(string s)
        {
            return this->searchpre(s)!=nullptr;
        }
    private:
        vector<Trie*> childs;
        bool flag;

};